package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/">二叉树的镜像</a>
 * <p>请完成一个函数，输入一个二叉树，该函数输出它的镜像。</p>
 * <pre>
 * 例如输入：
 *      4
 *
 *    /   \
 *
 *   2     7
 *
 *  / \   / \
 *
 * 1   3 6   9
 *
 * 镜像输出：
 *
 *      4
 *
 *    /   \
 *
 *   7     2
 *
 *  / \   / \
 *
 * 9   6 3   1
 * </pre>
 *
 * @author c2b
 * @since 2023/4/6 14:54
 */
public class JzOffer0027MirrorTree_S {

    /**
     * 使用队列：
     * <ol>
     *     <li>创建辅助队列，并将根节点加入到队列中</li>
     *     <li>从队列中弹出节点，将弹出节点的左右子节点分别入队，并交换左右子节点</li>
     *     <li>直到队列中元素为空</li>
     * </ol>
     */
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode currentNode = queue.poll();
            // 将左右子节点入队
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
            }
            // 交换左右子节点
            final TreeNode tempNode = currentNode.left;
            currentNode.left = currentNode.right;
            currentNode.right = tempNode;
        }
        return root;
    }

    /**
     * 递归
     */
    public TreeNode mirrorTree2(TreeNode root) {
        recursion(root);
        return root;
    }

    private void recursion(TreeNode currentNode) {
        // 递归的结束条件
        if (currentNode == null) {
            return;
        }
        // 交换左右子节点
        TreeNode tempNode = currentNode.left;
        currentNode.left = currentNode.right;
        currentNode.right = tempNode;
        recursion(currentNode.left);
        recursion(currentNode.right);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(4);
        node.left = new TreeNode(2);
        node.right = new TreeNode(7);
        node.left.left = new TreeNode(1);
        node.left.right = new TreeNode(3);
        node.right.left = new TreeNode(6);
        node.right.right = new TreeNode(9);
        TreeNode mirrorTree = new JzOffer0027MirrorTree_S().mirrorTree2(node);
        System.out.println(mirrorTree.val);


    }
}
